package implement

import (
	"container/list"
	"fmt"
)

type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	list     *list.List
}

type entry struct {
	key   int
	value int
}

func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		cache:    make(map[int]*list.Element),
		list:     list.New(),
	}
}

func (lru *LRUCache) Get(key int) int {
	if elem, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(elem) // Move the accessed element to the front
		return elem.Value.(*entry).value
	}
	return -1
}

func (lru *LRUCache) Put(key, value int) {
	if elem, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(elem) // Move the element to the front
		elem.Value.(*entry).value = value
		return
	}

	// If the cache is full, remove the least recently used item
	if lru.list.Len() == lru.capacity {
		backElem := lru.list.Back() // Get the last element
		if backElem != nil {
			lru.list.Remove(backElem)
			delete(lru.cache, backElem.Value.(*entry).key)
		}
	}

	// Add the new element to the front
	newElem := lru.list.PushFront(&entry{key, value})
	lru.cache[key] = newElem
}

// Display prints the current state of the cache (for debugging purposes).
func (lru *LRUCache) Display() {
	for e := lru.list.Front(); e != nil; e = e.Next() {
		entry := e.Value.(*entry)
		fmt.Printf("%d:%d ", entry.key, entry.value)
	}
	fmt.Println()
}
